package org.chnxi.datastructures.sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSorting {

    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2};
        int[] tmp = new int[arr.length];//归并排序需要一个额外的空间
        mergeSort(arr , 0 , arr.length - 1 , tmp);
        System.out.println("排序后："+ Arrays.toString(arr));

        System.out.println("测试大量数据的执行耗时：");
        int numCount = 80000;
        int[] randomArr = new int[numCount];
        for (int i =0; i<numCount; i++){
            randomArr[i] = (int) (Math.random()*numCount);
        }

        long start = System.currentTimeMillis();
        int[] randomArrTmp = new int[numCount];
        mergeSort(randomArr , 0 , randomArr.length-1, randomArrTmp);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));
    }

    /**
     * 分+合
     */
    public static void mergeSort(int[] arr , int left , int right , int[] tmp){
        if(left < right){
            int mid = (left + right) / 2;//中间索引
            //向左递归分解
            mergeSort(arr , left , mid , tmp);
            //向右递归分解
            mergeSort(arr , mid +1 , right , tmp);
            //合并
            merge(arr , left , mid , right , tmp);
        }
    }

    /**
     * 合并的方法
     * @param arr 排序的原始数组
     * @param left 左边有序索引的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param tmp 中转数组
     */
    public static void merge(int[] arr , int left ,int mid , int right , int[] tmp){
        int i = left;  //左边有序序列的初始索引
        int j = mid + 1;  //右边有序序列的初始索引
        int t = 0;  //指向tmp数组的当前索引

        //step1
        //先把左右两边的数据按照规则填充到tmp数组，直到左右两边的序列有一方处理完成
        while(i<=mid && j <= right){
            //如果左边的有序列的当前元素小于等于右边的有序序列的当前元素
            //即将左边当前的元素copy到tmp
            //然后t++,i++
            if(arr[i] <= arr[j]){
                tmp[t] = arr[i];
                t += 1;
                i += 1;
            }else{
                //反之，右边的有序序列的当前元素小于左边元素
                //将右边有序序列的当前元素，copy到tmp
                tmp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //step2
        //将有剩余的数据一边的数据依次全部填充到tmp
        while(i<=mid){//左边的有序序列还有剩余元素，将剩余元素copy到tmp
            tmp[t] = arr[i];
            t+=1;
            i+=1;
        }
        while(j<=right){//右边的有序序列还有剩余元素，将剩余元素copy到tmp
            tmp[t] = arr[j];
            t+=1;
            j+=1;
        }

        //step3
        //将tmp数组的元素全部copy到arr
        t=0;
        int tmpLeft = left;
        //第一次合并时，tmpLeft = 0; right = 1
        //第二次合并时，tmpLeft = 1l right = 3
        //最后一次合并时，tmpleft = 0,right = 7;
        //System.out.println("tmpLeft = "+tmpLeft +"right = "+right);
        while(tmpLeft <= right){
            arr[tmpLeft] = tmp[t];
            t+=1;
            tmpLeft+=1;
        }
    }
}
